La géométrie de la faisabilité
Pour un problème convexe avec des contraintes d'égalité $Ax=b$, un vecteur $v \in \mathbf{R}^n$ est une direction admissible si $Av = 0$. Cela signifie que se déplacer dans la direction $v$ préserve la contrainte : $A(x+v) = b$ si $Ax=b$.
Pour que $x^*$ soit optimal, le dérivée directionnelle $\nabla f(x^*)^T v$ doit être nulle pour toutes les directions admissibles $v$ dans le noyau $\mathcal{N}(A)$. Cela implique que le gradient $\nabla f(x^*)$ doit être orthogonal à $\mathcal{N}(A)$, ce qui conduit à l'existence des multiplicateurs de Lagrange.
Un point $x^*$ est optimal si et seulement s'il existe un vecteur $\nu^* \in \mathbb{R}^p$ tel que :
$\nabla f(x^*) + A^T \nu^* = 0$
Ceci forme un système d'équations linéaires qui caractérise l'équilibre entre la descente de l'objectif et la variété des contraintes.
Le gradient projeté
La projection euclidienne du gradient négatif $-\nabla f(x)$ sur le noyau $\mathcal{N}(A)$ est donnée par :
$\Delta x_{\text{pg}} = \text{argmin}_{Au=0} \| -\nabla f(x) - u \|_2$
Ce vecteur représente la "meilleure" direction de descente admissible. De façon cruciale, $x$ est optimal si et seulement si $\Delta x_{\text{pg}} = 0$.
Le système de KKT et les propriétés matricielles
Nous pouvons résoudre simultanément l'étape de Newton et les variables duales en utilisant le système par blocs :
$$\begin{bmatrix} I & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} v \\ w \end{bmatrix} = \begin{bmatrix} -\nabla f(x) \\ 0 \end{bmatrix}$$Remarque sur les propriétés spectrales de la matrice : La matrice de KKT est symétrique mais indéfinie. Si la matrice est non singulière, elle possède exactement $n$ valeurs propres positives et $p$ négatives. Cela implique que le point optimal $(x^*, \nu^*)$ est un point de selle de la fonction de Lagrange $L(x, \nu) = f(x) + \nu^T(Ax-b)$, plutôt qu'un minimum local simple dans l'espace primal-duel combiné.